package com.二叉树2;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Construct Binary Tree from Inorder and Postorder Traversal
 *
 * Solution
 * Given inorder and postorder traversal of a tree, construct the binary tree.
 *
 * Note:
 * You may assume that duplicates do not exist in the tree.
 *
 * For example, given
 *
 * inorder = [9,3,15,20,7]
 * postorder = [9,15,7,20,3]
 * Return the following binary tree:
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *    https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/942/
 */
public class 中序与后序构造二叉树 {
    static class Solution {

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            Map<Integer,Integer> map = new HashMap<>();
          for(int i =  0 ;i<inorder.length;i++){
              map.put(inorder[i],i);
          }
          //根节点
          TreeNode root  = new TreeNode(postorder[postorder.length-1]);
          Stack<TreeNode> stack = new Stack<>();
          stack.push(root);
          for(int i =  postorder.length-2;i>=0;i--){
              int val = postorder[i];
              TreeNode tmp = new TreeNode(val);
              //右节点
              if(map.get(val) > map.get(stack.peek().val)){
                  stack.peek().right = tmp;
              }
              //
              else{
                  TreeNode last  = null; //根节点
                  while (!stack.isEmpty() && map.get(val) < map.get(stack.peek().val)){
                      last = stack.pop();
                  }
                  last.left = tmp;

              }
              stack.push(tmp);
          }
          return root;
        }
        public TreeNode buildTree2(int[] inorder, int[] postorder) {
            if(postorder.length == 0) return null;
            Map<Integer,Integer> map = new HashMap<>();
            for(int i=0;i<inorder.length;++i) {
                map.put(inorder[i], i);
            }
            TreeNode root = new TreeNode(postorder[postorder.length-1]);
            Stack<TreeNode> st = new Stack<TreeNode>();
            st.push(root);
            for(int i=postorder.length-2;i>=0;--i){
                int x = postorder[i];
                TreeNode t  = new TreeNode(x);
                if(map.get(x) > map.get(st.peek().val)){
                    st.peek().right = t;
                }else{
                    TreeNode last = null;
                    while(!st.isEmpty() && map.get(st.peek().val) > map.get(x)){
                        last = st.pop();
                    }
                    last.left = t;
                }

                st.push(t);
            }
            return root;
        }


        public static void main(String[] args) {
            Solution solution = new Solution();
            TreeNode treeNode = solution.buildTree(new int[]{9,3,15,20,7}, new int[]{4,5,2,3,1});
        }
    }
}
